Bao

Rüdiger Klaehn

March 6, 2023

What is blake3

  • Cryptographic hash function
  • Evolution of the Blake2 family
  • One hash function, not a family
    • tagline one function, fast everywhere
  • XOF, KDF, PRF and MAC
  • Parallelism (SIMD and multithreading)

Fast

SIMD

Fewer rounds

How does it work

Chunks

  • Compute hash of chunk of up to 1024 bytes
  • Use of SIMD instructions

Larger files

  • binary tree to combine chunk hashes
  • lopsided
  • root gets special flag
  • multithreading
  • in blake3, binary tree is ephemeral

  • Persist branch hashes of binary tree
  • Verified streaming of entire data
  • Verified streaming of ranges
  • Outboard and inline mode

Verified streaming

  • Verify while receiving data
  • Wrong data will be discovered after 1 chunk

Data encoding

  • as you write it - post order
  • as you need it when encoding - pre order
  • finish / flip from post to pre order

Inline

  • 8 byte header, total size, le
  • 64 byte tree nodes, 2 hashes
  • 1024 byte data blocks, come in pairs
  • last block can be <1024 bytes

Outboard

  • 8 byte header, total size, le
  • 64 byte tree nodes, 2 hashes
  • Original file can remain unchanged

Slice encoding

  • encode just a slice of a large file
  • think HTML range requests
  • verified data and position

Chunk groups

Size proofs

  • You want to know total size

Size proofs and chunk groups

The End?

Don’t flip to pre-order?

  • keep outboard in post order
  • outboard is mostly append only
  • only changes in the end when appending
  • keep changing nodes separate?

∅ 𝕌